Leetcode-Two Sum

# Leetcode-Two Sum（两数之和）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

You may assume that each input would have exactly one solution, and you may not use the same element twice.

你可以按任意顺序返回答案。

You can return the answer in any order.

Example 1:

// Input: 
nums = [2,7,11,15], target = 9
// Output: 
	[0,1]
// Explanation: 
Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

// Input: 
  nums = [3,2,4], target = 6
// Output: 
    [1,2]

Example 3:

// Input: 
  nums = [3,3], target = 6
// Output: 
    [0,1]

# 解题

# 解题思路一：暴力枚举（暴力破解法）

最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。

当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
// 暴力破解法
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

// console.log(twoSum([2, 7, 11, 15], 9));

复杂度分析：

• 时间复杂度：O($N^2$)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：O(1)。

# 解题思路二：哈希表（哈希表法）

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  // 创建 Map 存储数组中的元素和下标
  map = new Map()
  // 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // x 存储目标元素 - 当前元素
    x = target - nums[i]
    // 如果 Map 中存在 x 则返回 [x, i]
    if (map.has(x)) {
      // map.get 获取到 x 的下标
      return [map.get(x), i]
    }
    // 将元素和下标存入 Map
    map.set(nums[i], i)
  }
};

// console.log(twoSum([2, 7, 11, 15], 9));